package com.example.demo.lintcode;

import org.junit.jupiter.api.Test;
import org.omg.PortableInterceptor.INACTIVE;

import java.util.*;

/**
 * *  Author:zlf
 * *  2020/10/19 10:24
 * <p>
 * * 24. LFU缓存  ，失败，执行时间太长
 * * 中文English
 * * LFU是一个著名的缓存算法
 * * 对于容量为k的缓存，如果缓存已满，并且需要逐出其中的密钥，则最少使用的密钥将被踢出。
 * * 实现LFU中的set 和 get
 * *================================两种特殊情况：===========================================
 * 情况1：set操作容器满时，频率最低的元素不是一个，删除最长时间没有访问过的，即按照到达该频率的时间为序，FIFO.
 * 情况2: 同样set操作，需要处理该元素已经在列表中情况，值修改，频率+1;
 * * 样例
 * * Input:
 * * LFUCache(3)
 * * set(2,2)
 * * set(1,1)
 * * get(2)
 * * get(1)
 * * get(2)
 * * set(3,3)
 * * set(4,4)
 * * get(3)
 * * get(2)
 * * get(1)
 * * get(4)
 * *
 * * Output:
 * * 2
 * * 1
 * * 2
 * * -1
 * * 2
 * * 1
 * * 4
 **/
public class LFUCache {
    private Map<Integer, Integer> map;
    private ArrayList<LFUCache.LFU> lfus = new ArrayList<>();
    private Map<Integer, Integer> listIndex = new HashMap<>();

    private int capacity;

    /*
     * @param capacity: An integer
     */
    public LFUCache(int capacity) {
        // do intialization if necessary
        this.capacity = capacity;
        map = new HashMap<>();
    }

    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void set(int key, int value) {
        // write your code here
        if (!map.containsKey(key)) {
            if (map.size() >= capacity) {
                LFUCache.LFU lfu = Collections.min(lfus);
                map.remove(lfu.getKey());
                lfus.remove(lfu);
                int index = listIndex.get(lfu.getKey());
                for (int i = index; i < lfus.size(); i++) {
                    LFUCache.LFU temp = lfus.get(i);
                    listIndex.put(temp.getKey(), listIndex.get(temp.getKey()) - 1);
                }
                listIndex.remove(lfu.getKey());
                lfus.add(new LFUCache.LFU(key, 0, 0));
                listIndex.put(key, lfus.size() - 1);
            } else {
                lfus.add(new LFUCache.LFU(key, 0, 0));
                listIndex.put(key, lfus.size() - 1);
            }
        } else {
            lfus.forEach(c -> {
                if (c.key == key) {
                    c.count++;
                }
            });
        }
        map.put(key, value);
    }

    /*
     * @param key: An integer
     * @return: An integer
     */
    public int get(int key) {
        // write your code here
        if (map.containsKey(key)) {
            LFUCache.LFU lfu = lfus.get(listIndex.get(key).intValue());
            lfu.count++;
            lfu.time = System.nanoTime();

            System.out.print(map.get(key));
            System.out.print(",");

            return map.get(key);
        } else
            System.out.print(-1);
        System.out.print(",");
        return -1;
    }

    public class LFU implements Comparable<LFUCache.LFU> {
        private int key;
        private int count;
        private long time;

        private LFU(int key, int count, long time) {
            this.key = key;
            this.count = count;
            this.time = time;
        }

        @Override
        public int compareTo(LFUCache.LFU o) {
            int i = this.count - o.count;//先按照年龄排序
            if (i == 0) {
                return (int) (this.time - o.time);//如果年龄相等了再用分数进行排序
            }
            return i;
        }

        public int getKey() {
            return key;
        }
    }
}
